from typing import List

INT_MAX = 10 ** 7


class Solution:
    def minDifficulty(self, jobs: List[int], days: int) -> int:
        size = len(jobs)

        if size < days:
            return -1

        difficulty_table = [[0] * size for _ in range(size)]
        for i in range(size):
            difficulty_table[i][i] = jobs[i]
            for j in range(i, size):
                difficulty_table[i][j] = max(difficulty_table[i][j - 1], jobs[j])

        # 定义状态矩阵：dp[d][j] = 在第d天结束时，下一个是第j个
        dp = [[INT_MAX] * (size + 1) for _ in range(days)]

        for i in range(size):
            dp[0][i + 1] = difficulty_table[0][i]

        for d in range(1, days):
            for j in range(1, size):
                for i in range(j):
                    dp[d][j + 1] = min(dp[d][j + 1], dp[d - 1][i + 1] + difficulty_table[i + 1][j])

        return dp[days - 1][size]


if __name__ == "__main__":
    print(Solution().minDifficulty(jobs=[6, 5, 4, 3, 2, 1], days=2))  # 7
    print(Solution().minDifficulty(jobs=[9, 9, 9], days=4))  # -1
    print(Solution().minDifficulty(jobs=[1, 1, 1], days=3))  # 3
    print(Solution().minDifficulty(jobs=[7, 1, 7, 1, 7, 1], days=3))  # 15
    print(Solution().minDifficulty(jobs=[11, 111, 22, 222, 33, 333, 44, 444], days=6))  # 843
